#include <vector>
#include <queue>

using namespace std;

class Solution
{
public:
    int find(vector<int> &nums, int left, int right, int k)
    {
        if (left == right)
        {
            return nums[left];
        }
        int l = left - 1, r = right + 1, x = nums[(left + right) >> 1];
        while (l < r)
        {
            do
            {
                l++;
            } while (nums[l] > x);

            do
            {
                r--;
            } while (nums[r] < x);

            if (l < r)
            {
                swap(nums[l], nums[r]);
            }
        }
        int endl = r - left + 1;
        if (k > endl)
        {
            return find(nums, r + 1, right, k - endl);
        }
        else
        {
            return find(nums, left, r, k);
        }
    }
    int findKthLargest(vector<int> &nums, int k)
    {
        return find(nums, 0, nums.size() - 1, k);
    }
};

